The modern communications era has brought about a tremendous expansion of wireline and wireless networks. Computer networks, television networks, and telephony networks are experiencing an unprecedented technological expansion, fueled by consumer demand. Wireless and mobile networking technologies have addressed related consumer demands, while providing more flexibility and immediacy of information transfer.
Current and future networking technologies continue to facilitate ease of information transfer and convenience to users. One area in which there is a demand to further improve the ease of information transfer and convenience to users involves improving the transmission of data over networks.
Although in traditional wireline networks the links between network nodes are generally long-lived, that is not always the case in mobile networking. In the case of mobile challenged networks, such as sensor, ad-hoc, opportunistic or disruption-tolerant networks, some, but not necessarily all, of the links between network nodes may be short-lived. The short-lived nature of some links between nodes may be caused by, for example: (1) network node mobility, such as in an ad-hoc Bluetooth® network comprised of devices temporarily in close proximity to each other which opportunistically form a network; (2) power saving settings, as in low-power devices, such as sensors, which generally stay in sleep mode most of the time and communicate only periodically; or (3) a difficult physical path, such as due to the nature of the terrain or in interplanetary or underwater communication where a communication link may be unreliable due to the long distance or difficult environment.
While such challenged networks might not present a problem in the communication of small amounts of data, today's mobile devices often send and receive large messages, such as, for example multimedia content. The transmission of such large messages presents several problems in challenged networks. For one, it may not be possible to send an entire message over a network link before the link expires. If only part of a message is successfully sent over a link prior to the link going down, when an alternative link between network nodes becomes available it is undesirable to resend portions of the message that have already been successfully sent as that would waste scarce network resources. In addition to problems of failed message transmissions and redundant transmissions leading to wasted network bandwidth, there are also concerns over corrupted data transmissions as well as security concerns as malicious messages designed to extract data from or disable a mobile device may be sent over a mobile network.
Traditionally, concerns over message authentication have been addressed by schemes which assume that messages are sent as one piece. One such scheme of message authentication is to calculate a hash over the entire contents of the message and sign the hash with the sender's private key. The sender then sends the message as one piece along with the signed hash. The receiver, after receiving the message, may then calculate the same hash from the message contents and verify the signature using the sender's public key in order to authenticate the message. This approach works well for traditional wired networks where data connections are reliable and long-lived, but in the case of short-lived wireless networks where it may be impossible to deliver the entire message during the life of the network link there is a need to allow for message fragmentation, which this approach does not support. For example, if the sender or an intermediary device fragments the original message but the receiver only receives a subset of the message fragments, the same hash cannot be calculated. Since the entire message is needed to calculate the same hash, the signature cannot be verified and the entire message will have to be sent again. Thus it is desirable to allow for fragmentation of the message into multiple fragments which may be individually authenticated.
One common approach allowing for fragmentation and individual authentication of each fragment is known as the signature list approach (also sometimes referred to as the toilet paper approach). In this approach a hash is calculated over each fragment and each hash is signed separately before being sent. This approach, however, has several shortcomings. Although the signature list approach allows for message fragmentation, it does not support on-demand fragmentation and reassembly by intermediary nodes. For example, a message may likely traverse several network nodes on a path from the sender to the receiver. Some of these nodes may be linked by reliable, long-lived links over which the entire message may be passed in one piece, while other nodes may be linked by short-lived links over which a message needs to be fragmented to ensure efficient transmission. Since the original sender cannot know whether short-lived links exist along the path the message is going to traverse in the network it is desirable to let each intermediary node individually decide whether the message should be sent to the next node in the path in fragments or in its entirety depending on the network link. Otherwise, if a message is fragmented when all links along the path are long-lived, limited network resources are wasted due to the increased authentication information in the form of attached signatures, which is not really needed. Contrastingly, if the message is not fragmented, but short-lived links exist along the path, network resources are also wasted by possibly having to resend the entire message when a link goes down.
The signature list approach also increases the amount of data that has to be sent over a link. For example, if a message is divided into n fragments (f1, f2 . . . fn) the message sender has to add n signatures to the message. Since signatures are relatively large, often in the order of one kilobyte or larger, adding n signatures causes a considerable bandwidth overhead. This approach also increases the computational work required by the sender and the receiver as the sender has to compute n signatures and the receiver has to verify n signatures. Signature creation and verification are computationally expensive operations and thus lead to a considerable computational overhead and waste of system resources.
Previously proposed by the inventors of the present invention as an improvement upon the signature list approach is the use of hash trees to authenticate message fragments. In this approach, the sender again divides a message into n fragments (f1, f2 . . . fn). A hash hi is then calculated for each fragment fi. Next, the sender constructs a hash tree from all of the fragment hashes (h1, h2 . . . hn) and creates a signature by signing the root node of the hash tree with its private key.
The sender sends each fragment separately as a self-contained unit by attaching to each fragment the signature and log2(n) hashes from the hash tree. The hashes sent with each fragment are selected so that the recipient can recalculate the same hash tree root node after having received the fragment. Thus, for a message divided into 8 fragments, each of the 8 fragments is sent separately accompanied by the signature and 3 hashes from the hash tree. The recipient then authenticates each received fragment independently by calculating the same hash tree root node from the received fragment itself and the received hashes of the hash tree and by verifying the signature on the root node.
This hash tree based approach offers an advantage over the signature list approach in that computational work is significantly reduced as for a message with n fragments the sender only has to create one signature and 2n−1 hashes, whereas in the signature list approach the sender has to create n signatures and n hashes, the creation of signatures being significantly more computationally expensive than the creation of hashes. Also, computational work is reduced on the recipient end since only one signature has to be verified. However, this hash tree based approach presents a disadvantage over the signature list approach in the form of increased bandwidth overhead. In the signature list approach each fragment must be accompanied with one signature, whereas in the hash tree approach each fragment must be accompanied with one signature and log2(n) hashes.
Accordingly, it would be advantageous to provide for an improved hash tree approach which allows for on-demand fragmentation of messages and reassembly of fragments but which produces minimum bandwidth overhead while utilizing the low computational overhead of a hash tree based approach.